package leetcode.f1t100;

import java.util.Arrays;

/**
 * 最大回文子串
 *
 * https://leetcode.com/problems/longest-palindromic-substring/
 *
 * @author lichx
 * @date 2021/9/24 13:37
 */
public class Q5_LongestPalindromicSubString {
    public String longestPalindrome(String s) {
//        return violent(s);
//        char[] c = s.toCharArray();
//        int L = 0;
//        int R = c.length;
//        while(L<=R){
//
//        }
        return better(s);
    }

    public String violent(String s){
        char[] c = s.toCharArray();
        int N = c.length;
        int ansBegin=0;
        int ansLength=1;
        for(int i =0;i<N;i++){
            for(int j =i+1;j<=N;j++){
                if(isPalindromic(c,i,j) && j-i > ansLength){
                    ansBegin = i;
                    ansLength = j-i;
                }
            }
        }
        return new String(Arrays.copyOfRange(c,ansBegin,ansBegin + ansLength));
    }
    //c[i...j) 是不是回文
    public boolean isPalindromic(char[]c,int i,int j){
        int L = i;
        int R = j-1;
        while(L<=R){
            if(c[L++] != c[R--]){
                return false;
            }
        }
        return true;
    }

    public String better(String s){
        char[] c = s.toCharArray();
        int ansBegin = 0;
        int ansLength = 1;
        for(int i=0,N = c.length;i<N;i++){
            int p1 = extendLR(c,i,i);
            int p2 = -1;
            if(i+1 < N && c[i]==c[i+1]){
                p2 = extendLR(c,i,i+1);
            }
            int betterP = Math.max(p1,p2);
            if(betterP > ansLength){
                ansLength = betterP;
                ansBegin = i - ((ansLength -1)>>1);
            }
        }
        return new String(Arrays.copyOfRange(c,ansBegin,ansBegin + ansLength));
    }
    public int extendLR(char[] c,int L,int R){
        int N = c.length;
        while(L>=0 && R < c.length && c[L] == c[R]){
            L--;
            R++;
        }
        return R-L-1;
    }

}
